package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         37,
		Discription: "解数独",
		Level:       3,
		Labels: map[string]int{
			"哈希表": 1,
			"回溯": 1,
			"递归": 1,
			"类数独": 1,
		},
	})
}

func SolveSudoku(board [][]byte) {
	var columns [9][9]bool
	var rows [9][9]bool
	var subAreas [3][3][9]bool
	var spaces [][2]int

	//先遍历一遍二维数组，确定已出现数组的位置、待填充的格子位置
	for i := 0; i < len(board[0]); i++ {
		for j := 0; j < len(board); j++ {
			if board[i][j] == '.' {
				spaces = append(spaces, [2]int{i, j})
				continue
			}

			num := board[i][j] - '1'
			columns[i][num] = true
			rows[j][num] = true
			subAreas[i/3][j/3][num] = true
		}
	}

	//回溯遍历待填充的格子
	bytes := []byte{'1', '2', '3', '4', '5', '6', '7', '8', '9'}
	var dfs func(k int) bool
	dfs = func(k int) bool {
		if k == len(spaces) {
			return true
		}

		x := spaces[k][0]
		y := spaces[k][1]
		for _, numByte := range bytes {
            num:=numByte-'1'
			if !columns[x][num] && !rows[y][num] && !subAreas[x/3][y/3][num] {
				board[x][y] = numByte
				columns[x][num] = true
				subAreas[x/3][y/3][num] = true
				rows[y][num] = true

				if dfs(k + 1) {
					return true
				}

				//如果不是解，恢复哈希表
				columns[x][num] = false
				subAreas[x/3][y/3][num] = false
				rows[y][num] = false
			}
		}

		return false
	}

	dfs(0)
}